There are many known approaches in which a new cipher is composed using a block cipher and hash function etc. as components. For instance, in encryption of storage devices such as a hard disk, research on composing a block cipher having a larger block size (such as 512 bits) corresponding to the size of the sector as a target block size using a block cipher having a standard block size (such as 128 bits) has been performed in order to facilitate the processing of encrypted data on a sector-by-sector basis.
Normally, security against a chosen-plaintext attack on a component is required in order to secure the sufficient security of a completed cipher in such a combination of encryption components. The “sufficient security” means security against any chosen-plaintext attack, or any attack arbitrarily combining a chosen-plaintext attack and chosen-ciphertext attack (simply called “chosen-ciphertext attack” hereinafter) when the target is a block cipher, and security against any chosen-plaintext attack based on a model in which the attacker can select an initial vector (abbreviated as “IV” hereinafter) when the target is a stream cipher.
In a cipher composed so as to theoretically guarantee security by using only secure components against any chosen-plaintext attack (PA) or chosen-ciphertext attack (CCA), its throughput (the processing amount per unit time) cannot exceed the throughput of the components. On the other hand, Non-Patent Document 1 [BIB-ARV] describes an approach that combines components meeting the standards of security with a weak definition, rather than use only secure components against any chosen-plaintext/ciphertext attack.
Non-Patent Document 1 [BIB-ARV] proposes an idea that achieves high security and high-speed operation by combining a relatively slow encryption process having high security and a high-speed encryption process having relatively weak security. More concretely, Non-Patent Document 1 [BIB-ARV] proposes to construct an additive stream cipher with an IV by expanding the output of a block cipher having the IV as input with another deterministic function func. The document indicates that, when the block cipher is secure against any chosen-plaintext attack and func is a secure pseudorandom generator, the constructed additive stream cipher with the IV is also secure against any chosen-IV attack in this case.
Here, the pseudorandom generator means a function in which, when the input is unknown uniform random numbers in a random input, it is difficult to quantitatively distinguish its output from the uniform random numbers, and security against chosen-plaintext attacks that judge the randomness of the output while adaptively selecting an input is not required.
Therefore, the pseudorandom generator is expected to operate faster than a component secure against chosen-plaintext attacks. As a matter of fact, the approach described in Non-Patent Document 1 [BIB-ARV] asymptotically makes the throughput of the target additive stream cipher with the IV the same as the throughput of the function func.
The goal of Non-Patent Document 1 [BIB-ARV] is to construct a stream cipher, however, a similar approach to block cipher is described in Non-Patent Document 2 [BIB-HYB]. More concretely, Non-Patent Document 2 describes a technique in which a block cipher with an arbitrary, large block size is composed by combining a block cipher secure against a combination of a chosen-plaintext attack and chosen-ciphertext attack (called “chosen-ciphertext attack” hereinafter) and a cipher (not always a block cipher) secure against any known-plaintext attack.
Further, Non-Patent Document 2 [BIB-HYB] describes a method (PRP; Pseudo-Random Permutation) in which a final composed cipher is only secure against chosen-plaintext attacks, and a method (SPRP; Strong Pseudo-Random Permutation) in which a final composed cipher is secure against chosen-ciphertext attacks. Below, we will consider a case in which the latter method (SPRP) is implemented using block cipher E of an n-bit block secure against any chosen-ciphertext attack, and cipher F with n-bit input and variable-length of output secure against any known-plaintext attack.
First, it is known that the cipher F can be realized by having a cipher with n-bit input/output secure against any known-plaintext attack operate in ICT (Increasing Chain Tree) mode described in Non-Patent Document 3 [BIB-ICT]. Therefore, in the case where a block cipher of an nm-bit block size secure against any chosen-ciphertext attack is composed using the method of Non-Patent Document 2 [BIB-HYB], an (m−2)n-bit output is obtained by calling the cipher E twice and the cipher F once.
Since a known-plaintext attack is weaker than a chosen-ciphertext attack, the cipher F is expected to be faster than the cipher E in terms of calculation amount per output block. Therefore, the throughput in the method of Non-Patent Document 2 [BIB-HYB] asymptotically coincides with the throughput of the cipher F.
The block cipher having a large block size secure against chosen-ciphertext attacks, which is realized by Non-Patent Document 2 [BIB-HYB], is effective for encrypting computer files, however, an additional parameter called “tweak” to the block cipher is sometimes required for general storage encryption.
The tweak is effective when storage is divided into a plurality of individual regions. For instance, in hard disk encryption, a disk is divided by a unit of (usually) 512 bytes called sector, and when they are encrypted, encryption is performed on a sector-by-sector basis. However, it is not preferable to encrypt every sector using the same key because the fact that the same information exists in different sectors will be leaked. Therefore, having the sector number as the tweak, encryption is performed so that the same plaintexts having different tweaks will be entirely different ciphertexts.
A parameter having such a property have been conventionally incorporated into several block ciphers, and Non-Patent Document 4 [BIB-LRW] theoretically formulates it. Further, a technique that composes an n-bit tweakable block cipher from a general n-bit block cipher without any tweak is described in Non-Patent Document 5 [BIB-XEX] in addition to Non-Patent Document 4 [BIB-LRW]. Here, when a block cipher with a tweak meets the security requirements defined by Non-Patent Document 5 [BIB-LRW], the block cipher is deemed “tweakable.”
Methods, described in Non-Patent Documents 6 [BIB-HCTR] and 7 [BIB-HCH], that compose a tweakable s-bit block cipher for an integer s equal to or greater than n using only an n-bit block cipher are known. These methods use a block cipher secure against any chosen-ciphertext attack as a black box, and their security against chosen-ciphertext attacks depends on the security of the used block cipher against chosen-ciphertext attacks.
Further, Non-Patent Document 8 [BIB-MMH] describes a method that realizes an AXU (Almost-XOR-Universal) hash function using a multi-modular hash function.
Non-Patent Document 9 [BIB-POLY] describes an algorithm that computes a product over a finite field at high speed.
Non-Patent Document 10 [BIB-AES] describes an example of a block cipher secure against any chosen-ciphertext attack.
Non-Patent Document 11 [BIB-GIL] describes the modified counter mode of a block cipher.
Non-Patent Document 12 [BIB-SEAL] describes a stream cipher SEAL. Non-Patent Document 13 [BIB-LEX] describes a stream cipher LEX based on AES of Non-Patent Document 10 [BIB-AES].
[Non-Patent Document 1]    [BIB-ARV]    W. Aiello, S. Rajagopalan, and R. Venkatesan, “High-Speed Pseudorandom Number Generation with Small Memory,” Fast Software Encryption, 6th International Workshop, FSE '99, Lecture Notes in Computer Science; Vol. 1636, March 1999
[Non-Patent Document 2]    [BIB-HYB]    K. Minematsu and Y. Ysunoo, “Hybrid Symmetric Encryption Using Known-Plaintext Attack-Secure Components,” pp. 242-260, Information Security and Cryptology-ICISC, 2002, 5th International Conference, Seoul, Korea, Nov. 28-29, 2002, Lecture Notes in Computer Science 2587, Springer, 2003, ISBN 3-540-00716-4
[Non-Patent Document 3]    [BIB-ICT]    U. Maurer and J. Sjoedin, “From Known-Plaintext to Chosen-Ciphertext Security,” Cryptology ePrint Archive 2006/071, http://eprint.iacr.org/2006/071.pdf
[Non-Patent Document 4]    [BIB-LRW]    M. Liskov, R. Rivest, and D. Wagner, “Tweakable Block Ciphers,” Advances in Cryptology-CRYPTO '02, LNCS 2442, pp. 31-46, 2002.
[Non-Patent Document 5]    [BIB-XEX]    P. Rogaway, “Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC,” Advances in Cryptology-ASIACRYPT '04, LNCS 3329, pp. 16-31, 2004.
[Non-Patent Document 6]    [BIB-HCTR]    P. Wang, D. Feng, and W. Wu, “HCTR: A Variable-Input-Length of Enciphering Mode,” pp. 175-188, Information Security and Cryptology, First SKLOIS Conference, CISC 2005, Proceedings, Lecture Notes in Computer Science 3822, Springer, 2005.
[Non-Patent Document 7]    [BIB-HCH]    D. Chakraborty and P. Sarkar, “HCH: A New Tweakable Enciphering Scheme Using the Hash-Encrypt-Hash Approach,” pp. 287-302, Progress in Cryptology-INDOCRYPT 2006, Proceedings, Lecture Notes in Computer Science 4329, Springer, 2006.
[Non-Patent Document 8]    [BIB-MMH]    S. Halevi and H. Krawczyk, “MMH: Software Message Authentication in the Gbit/second Rates,” Fast Software Cipher, 4th International Workshop, FSE '97, Lecture Notes in Computer Science; Vol. 1267, Springer, 1997, pp. 172-189
[Non-Patent Document 9]    [BIB-POLY]    D. J. Bernstein, “The Poly1305-AES Message Authentication Code,” Fast Software Encryption, FSE 2005, Lecture Notes in Computer Science 3557, pp. 32-49, Springer, 2005.
[Non-Patent Document 10]    [BIB-AES]    J. Daemen and V. Rijmen, “AES Proposal: Rijndael,” AES submission, 1998.
[Non-Patent Document 11]    [BIB-GIL]    H. Gilbert, “The Security of “One-Block-to-Many” Modes of Operation,” FSE 2003, Lecture Notes in Computer Science 2887, pp. 376-395, 2003.
[Non-Patent Document 12]    [BIB-SEAL]    P. Rogaway and D. Coppersmith, “A Software-Optimized Encryption Algorithm,” Fast Software Encryption, 1st International Workshop, FSE '93, Lecture Notes in Computer Science; Vol. 809, February 1993.
[Non-Patent Document 13]    [BIB-LEX]    A. Biryukov, “A New 128-bit Key Stream Cipher: LEX,” ECRYPT eStream project candidate, http://www.ecrypt.eu.org/stream/ciphers/lex/lex.pdf